#include <malloc.h>
#include <memory.h>

#ifdef NDEBUG
#undef NDEBUG
#include <assert.h>
#define NDEBUG
#else
#include <assert.h>
#endif

#include "../include/list.h"

struct list_node
{
    void* __data;
    struct list_node* __next;
    struct list_node* __prev;
};



/*
 * list_node interface
*/

inline struct list_node* list_node__construct(void* data, struct list_node* prev, struct list_node* next)
{
    struct list_node* new_list_node = (struct list_node*)malloc(sizeof(struct list_node));

    assert("Memory allocation error" && new_list_node != NULL);

    new_list_node->__data = data;
    new_list_node->__next = next;
    new_list_node->__prev = prev;

    return new_list_node;
}



/*
 * list interface
*/

inline void list__construct(struct list* list)
{
    assert("Passing NULL pointer to struct" && list != NULL);

    list->__head = NULL;
    list->__tail = NULL;
    list->__size = 0;
    list->__node_destructor = NULL;
}

inline void list__destruct(struct list* const list)
{
    list__clear(list);
}

void list__copy(struct list* dst, struct list* const src)
{
    if (!list__is_empty(dst))
    {
        list__destruct(dst);
    }

    struct list_node* node = src->__head;
    while (node = node->__next, node->__next)
    {
        list__add_back(dst, node->__data);
    }
}

void list__swap(struct list* lhs, struct list* rhs)
{
    assert("Attempting to swap with self" && lhs->__head != rhs->__head);

    struct list tmp;
    memcpy(&tmp, rhs, sizeof(struct list));
    memcpy(rhs, lhs, sizeof(struct list));
    memcpy(lhs, &tmp, sizeof(struct list));
}

void list__remove_front(struct list* list)
{
    assert("List is empty, nothing to remove" && !list__is_empty(list));

    struct list_node* node_to_destruct = list->__head;
    list->__head = list->__head->__next;

    if (list->__node_destructor)
    {
        list->__node_destructor(node_to_destruct);
    }
    free(node_to_destruct);
    list->__size--;
}

void list__remove_back(struct list* list)
{
    assert("List is empty, nothing to remove" && !list__is_empty(list));

    struct list_node* node_to_destruct = list->__tail;
    list->__tail = list->__tail->__prev;
    list->__tail->__next = NULL;

    if (list->__node_destructor)
    {
        list->__node_destructor(node_to_destruct);
    }
    free(node_to_destruct);
    list->__size--;
}

inline void list__clear(struct list* const list)
{
    while (!list__is_empty(list))
    {
        list__remove_front(list);
    }
}

void list__add_front(struct list* list, void* data)
{
    struct list_node* new_node = list_node__construct(data, NULL, list->__head);

    if (list__is_empty(list))
    {
        list->__tail = new_node;
    }
    else
    {
        list->__head->__prev = new_node;
    }

    list->__head = new_node;
    list->__size++;
}

void list__add_back(struct list* list, void* data)
{
    if (list__is_empty(list))
    {
        list__add_front(list, data);
    }
    else
    {
        list->__tail->__next = list_node__construct(data, list->__tail, NULL);
        list->__tail = list->__tail->__next;
        list->__size++;
    }
}

void list__merge_back(struct list* dst, struct list* const src)
{
    assert("Source list is empty, nothing to merge" && !list__is_empty(src));

    struct list new_list_part;
    list__construct(&new_list_part);
    list__swap(&new_list_part, src);
    list__destruct(src);

    dst->__tail->__next = new_list_part.__head;
    dst->__tail = new_list_part.__tail;
    dst->__size += list__size(&new_list_part);
}

void list__merge_front(struct list* dst, struct list* const src)
{
    assert("Source list is empty, nothing to merge" && !list__is_empty(src));

    struct list new_list_part;
    list__construct(&new_list_part);
    list__swap(&new_list_part, src);
    list__destruct(src);

    new_list_part.__tail->__next = dst->__head;
    dst->__head = new_list_part.__head;
    dst->__size += list__size(&new_list_part);
}

void list__remove_at(struct list* list, list_iterator_t pos)
{
    if (pos == list__begin(list))
    {
        list__remove_front(list);
    }
    else if (pos == list__end(list) || !(*pos)->__next)
    {
        list__remove_back(list);
    }
    else
    {
        assert("Source list is empty, nothing to remove" && !list__is_empty(list));

        struct list_node* node_to_destruct = *pos;
        (*pos)->__prev->__next = (*pos)->__next;
        (*pos)->__next->__next = (*pos)->__prev;

        if (list->__node_destructor)
        {
            list->__node_destructor(node_to_destruct);
        }

        free(node_to_destruct);
        list->__size--;
    }
}

inline void list__remove_after(struct list* list, list_iterator_t pos)
{
    if (*pos)
    {
        list_iterator__next(&pos);
    }
    list__remove_at(list, pos);
}

inline void list__remove_before(struct list* list, list_iterator_t pos)
{
    if (*pos && (*pos)->__prev)
    {
        list_reverse_iterator__next(&pos);
    }
    list__remove_at(list, pos);
}

void list__insert_at(struct list* list, void* data, list_iterator_t pos)
{
    if (pos == list__begin(list))
    {
        list__add_front(list, data);
    }
    else if (pos == list__end(list) || !(*pos)->__next)
    {
        list__add_back(list, data);
    }
    else
    {
        *pos = list_node__construct(data, (*pos)->__prev, *pos);
        list->__size++;
    }
}

inline void list__insert_after(struct list* list, void* data, list_iterator_t pos)
{
    if (*pos)
    {
        list_iterator__next(&pos);
    }
    list__insert_at(list, data, pos);
}

inline void list__insert_before(struct list* list, void* data, list_iterator_t pos)
{
    if (*pos && (*pos)->__prev)
    {
        list_reverse_iterator__next(&pos);
    }
    list__insert_at(list, data, pos);
}

void list__merge_at(struct list* dst, struct list* const src, list_iterator_t pos)
{
    if (pos == list__begin(dst))
    {
        list__merge_front(dst, src);
    }
    else if (pos == list__end(dst) || !(*pos)->__next)
    {
        list__merge_back(dst, src);
    }
    else
    {
        assert("Source list is empty, nothing to merge" && !list__is_empty(src));

        struct list new_list_part;
        list__construct(&new_list_part);
        list__swap(&new_list_part, src);
        list__destruct(src);

        new_list_part.__tail->__next = *pos;
        *pos = new_list_part.__head;

        dst->__size += list__size(&new_list_part);
    }
}

inline void list__merge_after(struct list* dst, struct list* const src, list_iterator_t pos)
{
    if (*pos)
    {
        list_iterator__next(&pos);
    }
    list__merge_at(dst, src, pos);
}

inline void list__merge_before(struct list* dst, struct list* const src, list_iterator_t pos)
{
    if (*pos && (*pos)->__prev)
    {
        list_reverse_iterator__next(&pos);
    }
    list__merge_at(dst, src, pos);
}



/*
 * list getters and setters
*/

inline size_t list__size(struct list* const list)
{
    return list->__size;
}

inline int list__is_empty(struct list* const list)
{
    return list->__head == NULL;
}

inline void* list__get_at(struct list* const list, size_t index)
{
    return *list__get_at_addr(list, index);
}

inline void* list__get_front(struct list* const list)
{
    return *list__get_front_addr(list);
}

inline void* list__get_back(struct list* const list)
{
    return *list__get_back_addr(list);
}

inline const void* list__get_at_const(struct list* const list, size_t index)
{
    return (const void*)(*list__get_at_addr(list, index));
}

inline const void* list__get_front_const(struct list* const list)
{
    return (const void*)(*list__get_front_addr(list));
}

inline const void* list__get_back_const(struct list* const list)
{
    return (const void*)(*list__get_back_addr(list));
}

void** list__get_at_addr(struct list* const list, size_t index)
{
    assert("Index out of range" && index < list__size(list));

    if (index == 0)
    {
        return list__get_front_addr(list);
    }
    else if (index == (list__size(list) - 1))
    {
        return list__get_back_addr(list);
    }
    else
    {
        list_iterator_t iter = list__begin(list);
        list_iterator__advance(&iter, index);
        return list_iterator__extract_data_addr(iter);
    }
}

inline void** list__get_front_addr(struct list* const list)
{
    assert("Dereference NULL pointer (no data)" && !list__is_empty(list));
    return &list->__head->__data;
}

inline void** list__get_back_addr(struct list* const list)
{
    assert("Dereference NULL pointer (no data)" && !list__is_empty(list));
    return &list->__tail->__data;
}

inline const void** list__get_at_addr_const(struct list* const list, size_t index)
{
    return (const void**)list__get_at_addr(list, index);
}

inline const void** list__get_front_addr_const(struct list* const list)
{
    return (const void**)list__get_front_addr(list);
}

inline const void** list__get_back_addr_const(struct list* const list)
{
    return (const void**)list__get_back_addr(list);
}

inline void list__set_node_destructor(struct list* list, list_node_destructor_t node_destructor)
{
    list->__node_destructor = node_destructor;
}

inline list_iterator_t list__begin(struct list* const list)
{
    return &list->__head;
}

inline list_iterator_t list__end(struct list* const list)
{
    return &list->__tail->__next;
}

inline list_reverse_iterator_t list__reverse_begin(struct list* const list)
{
    return list__begin(list);
}

inline list_reverse_iterator_t list__reverse_end(struct list* const list)
{
    return list__end(list);
}

list_iterator_t __list__find_impl(struct list* const list, void* data, size_t type_size)
{
    list_iterator_t iter = list__begin(list);
    for (; iter != list__end(list) && memcmp(list_iterator__extract_data_addr(iter), &data, type_size);
         list_iterator__next(&iter))
         ;
    return iter;
}

list_iterator_t list__find_if(struct list* const list, int(*predicate)(void* data))
{
    list_iterator_t iter = list__begin(list);
    for (; iter != list__end(list) && !predicate(list_iterator__extract_data(iter));
         list_iterator__next(&iter))
        ;
    return iter;
}



/*
 * list iterator functions
*/

inline list_iterator_t list_iterator__next(list_iterator_t* iter)
{
    *iter = &(**iter)->__next;
    return *iter;
}

inline list_iterator_t list_iterator__advance(list_iterator_t* iter, size_t n)
{
    while (list_iterator__next(iter), n--)
        ;
    return *iter;
}

inline list_reverse_iterator_t list_reverse_iterator__next(list_reverse_iterator_t* iter)
{
    *iter = &(**iter)->__prev;
    return *iter;
}

inline list_reverse_iterator_t list_reverse_iterator__advance(list_reverse_iterator_t* iter, size_t n)
{
    while (list_reverse_iterator__next(iter), n--)
        ;
    return *iter;
}

inline void* list_iterator__extract_data(list_iterator_t iter)
{
    return *list_iterator__extract_data_addr(iter);
}

inline void** list_iterator__extract_data_addr(list_iterator_t iter)
{
    return &(*iter)->__data;
}
